package main

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
两数之和
*/
func twoSum(nums []int, target int) []int {
	// 第一种，暴力解法
	/*	for i, num := range nums {
			for b := i + 1; b < len(nums); b++ {
				if num+nums[b] == target {
					return []int{i, b}
				}
			}
		}
		return nil*/

	// 第二种 利用map，可以缩短第二轮遍历的时间
	m := make(map[int]int)
	for i, num := range nums {
		if i2, ok := m[target-num]; ok {
			if i != i2 {
				return []int{i, i2}
			}
		}
		m[num] = i
	}
	return nil
}

/**
两数相加,
*/
func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
	// 保存单向脸部的最后一个的内存地址
	var tail *ListNode
	var sum int
	for {
		n1, n2 := 0, 0
		// 链表可能不能等长的，所以需要对每一个单独处理
		if l1 != nil {
			n1 = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			n2 = l2.Val
			l2 = l2.Next
		}
		// 计算总和
		sum = n1 + n2 + sum/10
		if head == nil {
			// 如果是第一次，则需要创建内存存储数据，并赋值到tail最后的节点上
			head = &ListNode{sum % 10, nil}
			tail = head
		} else {
			// 如果不是第一次，则创建一个内存，存储数据
			tail.Next = &ListNode{sum % 10, nil}
			tail = tail.Next
		}
		// 如果都为空，并且最高位小于9这不需要进行下一步
		if l1 == nil && l2 == nil {
			if sum >= 10 {
			} else {
				return head
			}

		}
	}
}

/**
无重复字符的最长子串
*/
func lengthOfLongestSubstring(s string) int {
	//println("------------------------------------------------------------")
	// 记录当前窗口的位置和上一个窗口的位置
	start, maxLength := 0, 0
	m := make(map[byte]int, len(s)-1)
	for endIndex, data := range s {
		// 如果存在，
		if _, ok := m[byte(data)]; ok {
			maxLength = endIndex - start
		} else {
			m[byte(data)] = endIndex
			// 如果是最后一个且不重复需要重新另算
			if endIndex == len(s)-1 && maxLength < len(s)-start {
				maxLength = len(s) - start
			}
		}
	}
	return maxLength
}
